package structures.tree
{

	public class BinarySearchTree implements IBinarySearchTree
	{
		public function BinarySearchTree()
		{
		}

		private var _rootBinaryNode:BinaryNode;

		public function setRoot(value:int):void
		{
			if (!_rootBinaryNode)
			{
				_rootBinaryNode=new BinaryNode;
				_rootBinaryNode.num=value;
			}
		}

		public function contains(value:int):Boolean
		{
			return containsInNode(value, _rootBinaryNode) ? true : false;
		}

		private function containsInNode(value:int, parentNode:BinaryNode):BinaryNode
		{
			if (parentNode == null)
				return null;

			if (parentNode.num == value)
				return parentNode;
			else if (value < parentNode.num)
				return containsInNode(value, parentNode.leftBinaryNode);
			else
				return containsInNode(value, parentNode.rightBinaryNode);
		}

		public function findMax():int
		{
			var curNode:BinaryNode=_rootBinaryNode;
			while (curNode.rightBinaryNode != null)
			{
				curNode=curNode.rightBinaryNode;
			}
			return curNode.num;
		}

		public function findMin():int
		{
			var curNode:BinaryNode=_rootBinaryNode;
			while (curNode.leftBinaryNode != null)
			{
				curNode=curNode.leftBinaryNode;
			}
			return curNode.num;
		}

		public function insert(value:int):void
		{
			insertInNode(value, _rootBinaryNode);
		}

		private function insertInNode(value:int, parentNode:BinaryNode):void
		{
			if (parentNode.num == value)
			{
				return
			}
			else if (parentNode.num > value)
			{
				if (parentNode.leftBinaryNode)
				{
					insertInNode(value, parentNode.leftBinaryNode);
				}
				else
				{
					parentNode.leftBinaryNode=new BinaryNode;
					parentNode.leftBinaryNode.num=value;
				}
			}
			else
			{
				if (parentNode.rightBinaryNode)
				{
					insertInNode(value, parentNode.rightBinaryNode);
				}
				else
				{
					parentNode.rightBinaryNode=new BinaryNode;
					parentNode.rightBinaryNode.num=value;
				}
			}

		}

		public function remove(value:int):void
		{
			//TODO Auto-generated method stub
		}
	}
}
